package xyz.naokeziteng.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 169题：多数元素
 */
public class MajorityElement {

    public int majorityElement(int[] nums) {
        //次数
        int numot = nums.length / 2;

        Arrays.sort(nums);

        int result = nums[0];
        int times = 1;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == result) {
                times++;
            } else {
                result = nums[i];
                times = 1;
            }

            if (times > numot) {
                break;
            }
        }

        return result;
    }

    public int majorityElementV2(int[] nums) {
        //次数
        int numot = nums.length / 2;

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.get(nums[i]) == null) {
                map.put(nums[i], 1);
            } else {
                map.put(nums[i], map.get(nums[i]) + 1);
            }
            if (map.get(nums[i]) > numot) {
                return nums[i];
            }
        }

        return -1;

    }
}
